package org.bear.graph.base;


// 994. 腐烂的橘子
/*
d值 默认为3
1. 从腐烂的橘开始，向四周新鲜的橘子扩散 每前进一步 d值加1
2. 碰到空单元格 腐烂的橘子 则停止
3. 碰到d值比自己小于等于的单元格 则停止
再次遍历一遍单元格 查看是否有新鲜的 有的话返回-1 ，同时对于大于2的值 求最大值
 */
public class OrangesRotting {
    int[][] grid;
    public int orangesRotting(int[][] grid) {
        this.grid = grid;
        if (grid.length==0) return -1;
        for (int i=0;i<grid.length;i++){
            for (int j=0;j<grid[0].length;j++){
                if (grid[i][j]==2){
                    dismiss(i, j, 2);
                }
            }
        }

        int max=2;
        for (int i=0;i<grid.length;i++){
            for (int j=0;j<grid[0].length;j++){
                if (grid[i][j]==1){
                    return -1;
                }
                max=Math.max(max, grid[i][j]);
            }
        }

        return max-2;
    }

    private void dismiss(int i, int j, int d) {
        if (grid[i][j]==0){// 空单元格
        }else if (grid[i][j]==1){// 新鲜橘子
            grid[i][j] = d;
            doDismiss(i, j,d+1);
        }else if (grid[i][j]==2){ // 腐烂的橘子
            if (d==2){
                doDismiss(i, j,d+1);
            }
        }else if(d<grid[i][j]){
            grid[i][j] = d;
            doDismiss(i, j,d+1);
        }
    }

    private void doDismiss(int i, int j, int d) {
        if (i-1>=0){
            dismiss(i-1, j, d);
        }
        if (i+1<grid.length){
            dismiss(i+1, j, d);
        }
        if (j-1>=0){
            dismiss(i, j-1, d);
        }
        if (j+1<grid[0].length){
            dismiss(i, j+1, d);
        }
    }
}
